package 左哥算法.ch10暴力递归;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * N皇后问题
 *  按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
 *  n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *  给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 *
 * 递归思路：
 *  尝试从第一行放入皇后，当这一行符合要求时，则在下一行放入皇后。
 *  如果下一行的某一列可以放入皇后，则到下下行，直到最后一行，如果最后行也能放入皇后，则解法+1，然后回退到上一行，清除掉下一行的皇后，查看下一列是否有其他解法
 *  如果某一行所有列都不能放入皇后，则回退到上一行，清除掉刚刚下面几行的皇后，更换上一行的列数，如果上上行所有列也无法满足，则到上上行。
 *  直到第一行所有列都无法满足，则得到所有解法
 *
 *
 *  从棋盘第一行尝试放入皇后，即 f(0)
 *  f(0)无法给出具体有多少解，只能判断当前行
 *
 */
public class Ch10_八皇后问题 {

    public static void main(String[] args) {
        Ch10_八皇后问题 test = new Ch10_八皇后问题();
        List<List<String>> lists = test.solveNQueens(8);
/*        String[][] arrays = {
                {"Q","","","","","","",""},
                {"","","Q","","","","",""},
                {"","","","","","","",""},
                {"","","","","","","",""},
                {"","","","","","","",""},
                {"","","","","","","",""},
                {"","","","","","","",""},
                {"","","","","","","",""},
        };
        System.out.println(verify(arrays, 2, 1));*/
    }

    /**
     * 总共有多少种解法
     */
    private int res;

    /**
     * @param n:皇后数量
     * @return  原本是返回具体的解法
     */
    public List<List<String>> solveNQueens(int n) {
        String[][] arrays = new String[n][n];
        String[] strings = new String[n];
        Arrays.fill(strings,".");
        for (int i = 0; i < arrays.length; i++) {
            arrays[i]=strings.clone();
        }
        List<List<String>> lists = backTracking(arrays, 0);
        System.out.println(res);
        return lists;
    }

    /**
     * @param arrays：存放皇后的数组
     * @param row：从第几行开始回溯
     * @return
     */
    public List<List<String>> backTracking(String[][] arrays,int row){
        List<List<String>> resList=new ArrayList<>();
        for (int col=0;col<arrays.length;col++){
            if (verify(arrays,row,col)){
                arrays[row][col]="Q";
                if (row+1==arrays.length){ //最后一行也符合
                    res++;
                    System.out.println("--------分隔符："+res+"---------");
                    String str="";
                    List<String> list=new ArrayList<>();
                    for (String[] array : arrays) {
                        list.add(String.join("",array));
                        System.out.println(Arrays.toString(array));
                    }
                    resList.add(list);
                    return resList;
                }
                resList.addAll(backTracking(arrays, row + 1));
                for (int i = row; i < arrays.length; i++) {
                    Arrays.fill(arrays[i],".");
                }
            }
        }
        return resList;
    }

    /**
     * 验证放入皇后后，当前棋盘是否符合要求
     * @param arrays：当前棋盘
     * @param row：放入皇后的行
     * @param col：放入皇后的列
     * @return：是否符合要求
     */
    public static boolean verify(String[][] arrays,int row,int col){
        //验证同一行是否符合要求（不存在皇后），因为行每次都会跳入下一行，所以可以不判断
//        for (int curr=0;curr<arrays.length;curr++){
//            if (curr==col)continue;
//            if (arrays[row][curr].equals("Q")){
//                return false;
//            }
//        }
        //验证同一列是否符合要求（不存在皇后）
        for (int curr=0;curr<arrays.length;curr++){
            if (curr==row)continue;
            if (arrays[curr][col].equals("Q")){
                return false;
            }
        }
        //获取对角线最左侧的坐标
        int i=0,j=0;
        if (row>col){
            i=row-col;
        }else {
            j=col-row;
        }
        //验证左对角线是否符合要求
        for (;i<arrays.length&&j<arrays.length;i++,j++){
            if (i==row&&j==col)continue;
            if (arrays[i][j].equals("Q")){
                return false;
            }
        }
        //获取右对角线最右侧的坐标
        i=0;j=arrays.length-1;
        if (row>j-col){
             i=row-(j-col);
        }else {
            j=row+col;
        }
        //验证右对角线是否符合要求
        for (;i<arrays.length&&j>=0;i++,j--){
            if (i==row&&j==col)continue;
            if (arrays[i][j].equals("Q")){
                return false;
            }
        }
        return true;
    }
}

